<?php
/**
 * User: LRZ
 * Date: 2020/2/21
 * Time: 17:05
 */

/**
 *  868.二进制间距
 *
 *  标签：数学
 *
 *  给定一个正整数 N，找到并返回 N 的二进制表示中两个连续的 1 之间的最长距离。 
 *  如果没有两个连续的 1，返回 0 。
 *
 *  示例 1：
 *      输入：22
 *      输出：2
 *      解释：
 *          22 的二进制是 0b10110 。
 *          在 22 的二进制表示中，有三个 1，组成两对连续的 1 。
 *          第一对连续的 1 中，两个 1 之间的距离为 2 。
 *          第二对连续的 1 中，两个 1 之间的距离为 1 。
 *          答案取两个距离之中最大的，也就是 2 。
 *
 *  示例 2：
 *      输入：5
 *      输出：2
 *      解释：5 的二进制是 0b101 。
 *
 *  示例 3：
 *      输入：6
 *      输出：1
 *      解释：6 的二进制是 0b110 。
 *
 *  示例 4：
 *      输入：8
 *      输出：0
 *      解释：8 的二进制是 0b1000 。在 8 的二进制表示中没有连续的 1，所以返回 0 。
 *   
 *  提示：1 <= N <= 10^9
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/binary-gap
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$N   = 22;
$res = binaryGap($N);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function binaryGap($N)
{
    $binN  = decbin($N);
    $size  = strlen($binN);
    $array = [];
    for ($i = 0; $i < $size; $i++) {
        if ($binN[$i] === '1') {
            $array[] = $i;
        }
    }
    $res = 0;
    for ($i = 0; $i < count($array) - 1; $i++) {
        $res = max($res, $array[$i + 1] - $array[$i]);
    }
    return $res;
}